여덟 퀸 문제

1. 개요

1.1. 해답

2. n-Queens 문제

2.1. n-Queens 문제의 해2.2. n-Queens 문제와 백트래킹 방법

1. 개요 [편집]

여덟 퀸 문제는 8x8 체스판에 8개의 퀸을 배치하는 문제다. 이 때 어떤 퀸도 다른 퀸을 위협해서는 안된다는 조건이 있다. 1848년 막스 베첼이 처음으로 제안한 퍼즐 문제로, 수학과 컴퓨터 과학에서 알고리즘 문제로 많이 거론된다.

1.1. 해답 [편집]

파일:8퀸 문제 해법.png
위와 같이 12개의 기본 형태가 있으며, 이를 근본해라고 한다. 대칭인 마지막 패턴(4개)을 제외하고 각 8개를 대칭이동으로 만들 수 있으므로, 여덟 퀸의 경우 총 92개의 해가 있다.

2. n-Queens 문제 [편집]

n-Queens 문제는 n개의 여왕말을 nxn 체스판에 서로 위협하지 않도록 배치하는 문제로서, 여덟 퀸 문제를 일반화한 알고리즘 문제다. 일반화된 n-Queens 문제에 대한 해법으로는, n이 2, 3인 경우를 제외하고 모든 자연수에서 해를 찾을 수 있다.

2.1. n-Queens 문제의 해 [편집]

n개의 퀸을 nxn 체스판에 나타내는 해의 수는 n에 따라 달라진다. 고유한 해(대칭인 해를 제외한 해)는 온라인 정수열 사전(OEIS)에서 수열 A002562로 등록되어 있다. 일반적인 해(대칭을 구별하는 해)는 OEIS의 수열 A000170으로 등록되어 있다.

2.2. n-Queens 문제와 백트래킹 방법 [편집]

n-Queens 문제는 알고리즘 설계 기법 중 하나인 백트래킹 방법으로 해결한다. 아래는 백트래킹으로 n-Queens 문제를 해결하는 파이썬 구현 소스 코드이다.

def n_queens (i, col):
    n = len(col) -1
    if (promising(col, i)):
        if (i == n):
        print(col[1: n + 1])
    else:
        for j in range(1, n+1)
        col[i + 1] = j
        n_queens(col, i + 1)

def promising (i, col):
    k = 1
    flag = True
    while (k < i and flag):
    if (col[i] == col[k] or abs(col[i] - col[k]) == (i - k)):
        flag = False
        k += 1
    return flag

n-Queens 문제를 백트래킹으로 푸는 방법은 이 영상 [1]에 자세히 나오고, 위 소스 코드 구현에 대한 설명은 이 영상 [2]에 나와 있다.

[1] 백트래킹과 n-Queens 문제[2] n-Queens 문제의 구현